#include "regexp.h"
#include <stdio.h>
#include <ctype.h>

#ifndef ultrix
#include <stdlib.h>
#endif

#include <string.h>

#define END 0
#define BOL 1
#define EOL 2
#define ANY 3
#define ANYOF 4
#define ANYBUT  5
#define BRANCH  6
#define BACK  7
#define EXACTLY 8
#define NOTHING 9
#define STAR  10
#define PLUS  11
#define WORDA 12
#define WORDZ 13
#define OPEN  20
#define CLOSE 30

#define OP(p) (*(p))
#define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
#define OPERAND(p)  ((p) + 3)
#define UCHARAT(p)  ((int)*(unsigned char *)(p))
#define FAIL(m) { my_regerror(m); return(NULL); }
#define ISMULT(c) ((c) == '*' || (c) == '+' || (c) == '?')

#define HASWIDTH  01
#define SIMPLE    02
#define SPSTART   04
#define WORST   0

static char *regparse;
static int regnpar;
static char regdummy;
static char *regcode;
static long regsize;

#ifndef STATIC
#define STATIC  static
#endif
STATIC char *reg( int paren, int *flagp );
STATIC char *regbranch( int *flagp );
STATIC char *regpiece( int *flagp );
STATIC char *regatom( int *flagp );
STATIC char *regnode( int op );
STATIC char *regnext( register char *p );
STATIC void regc( int b );
STATIC void reginsert( char op, char *opnd );
STATIC void regtail( char *p, char *val );
STATIC void regoptail( char *p, char *val );

regexp * my_regcomp( const char *exp ) {
  register regexp *r;
  register char *scan;
  register char *longest;
  register unsigned len;
  int flags;
  if( exp == NULL ) {
    FAIL( "NULL argument" );
  }
  regparse = ( char * )exp;
  regnpar = 1;
  regsize = 0L;
  regcode = &regdummy;
  regc( MAGIC );
  if( reg( 0, &flags ) == NULL ) {
    return( NULL );
  }
  if( regsize >= 32767L ) {
    FAIL( "regexp too big" );
  }
  r = ( regexp * )malloc( sizeof( regexp ) + ( unsigned )regsize );
  if( r == NULL ) {
    FAIL( "out of space" );
  }
  regparse = ( char * )exp;
  regnpar = 1;
  regcode = r->program;
  regc( MAGIC );
  if( reg( 0, &flags ) == NULL ) {
    free( r );
    return( NULL );
  }
  r->regstart = '\0';
  r->reganch = 0;
  r->regmust = NULL;
  r->regmlen = 0;
  scan = r->program + 1;
  if( OP( regnext( scan ) ) == END ) {
    scan = OPERAND( scan );
    if( OP( scan ) == EXACTLY ) {
      r->regstart = *OPERAND( scan );
    } else if( OP( scan ) == BOL ) {
      r->reganch++;
    }
    if( flags & SPSTART ) {
      longest = NULL;
      len = 0;
      for( ; scan != NULL; scan = regnext( scan ) )
        if( OP( scan ) == EXACTLY && strlen( OPERAND( scan ) ) >= len ) {
          longest = OPERAND( scan );
          len = strlen( OPERAND( scan ) );
        }
      r->regmust = longest;
      r->regmlen = len;
    }
  }
  return( r );
}

static char * reg( int paren, int *flagp ) {
  register char *ret;
  register char *br;
  register char *ender;
  register int parno = 0;
  int flags;
  *flagp = HASWIDTH;
  if( paren ) {
    if( regnpar >= NSUBEXP ) {
      FAIL( "too many ()" );
    }
    parno = regnpar;
    regnpar++;
    ret = regnode( OPEN + parno );
  } else {
    ret = NULL;
  }
  br = regbranch( &flags );
  if( br == NULL ) {
    return( NULL );
  }
  if( ret != NULL ) {
    regtail( ret, br );
  } else {
    ret = br;
  }
  if( !( flags & HASWIDTH ) ) {
    *flagp &= ~HASWIDTH;
  }
  *flagp |= flags & SPSTART;
  while( *regparse == '|' || *regparse == '\n' ) {
    regparse++;
    br = regbranch( &flags );
    if( br == NULL ) {
      return( NULL );
    }
    regtail( ret, br );
    if( !( flags & HASWIDTH ) ) {
      *flagp &= ~HASWIDTH;
    }
    *flagp |= flags & SPSTART;
  }
  ender = regnode( ( paren ) ? CLOSE + parno : END );
  regtail( ret, ender );
  for( br = ret; br != NULL; br = regnext( br ) ) {
    regoptail( br, ender );
  }
  if( paren && *regparse++ != ')' ) {
    FAIL( "unmatched ()" );
  } else if( !paren && *regparse != '\0' ) {
    if( *regparse == ')' ) {
      FAIL( "unmatched ()" );
    } else
    { FAIL( "junk on end" ); }
  }
  return( ret );
}

static char * regbranch( int *flagp ) {
  register char *ret;
  register char *chain;
  register char *latest;
  int flags;
  *flagp = WORST;
  ret = regnode( BRANCH );
  chain = NULL;
  while( *regparse != '\0' && *regparse != ')' &&
         *regparse != '\n' && *regparse != '|' ) {
    latest = regpiece( &flags );
    if( latest == NULL ) {
      return( NULL );
    }
    *flagp |= flags & HASWIDTH;
    if( chain == NULL ) {
      *flagp |= flags & SPSTART;
    } else
    { regtail( chain, latest ); }
    chain = latest;
  }
  if( chain == NULL ) {
    ( void ) regnode( NOTHING );
  }
  return( ret );
}

static char * regpiece( int *flagp ) {
  register char *ret;
  register char op;
  register char *next;
  int flags;
  ret = regatom( &flags );
  if( ret == NULL ) {
    return( NULL );
  }
  op = *regparse;
  if( !ISMULT( op ) ) {
    *flagp = flags;
    return( ret );
  }
  if( !( flags & HASWIDTH ) && op != '?' ) {
    FAIL( "*+ operand could be empty" );
  }
  *flagp = ( op != '+' ) ? ( WORST | SPSTART ) : ( WORST | HASWIDTH );
  if( op == '*' && ( flags & SIMPLE ) ) {
    reginsert( STAR, ret );
  } else if( op == '*' ) {
    reginsert( BRANCH, ret );
    regoptail( ret, regnode( BACK ) );
    regoptail( ret, ret );
    regtail( ret, regnode( BRANCH ) );
    regtail( ret, regnode( NOTHING ) );
  } else if( op == '+' && ( flags & SIMPLE ) ) {
    reginsert( PLUS, ret );
  } else if( op == '+' ) {
    next = regnode( BRANCH );
    regtail( ret, next );
    regtail( regnode( BACK ), ret );
    regtail( next, regnode( BRANCH ) );
    regtail( ret, regnode( NOTHING ) );
  } else if( op == '?' ) {
    reginsert( BRANCH, ret );
    regtail( ret, regnode( BRANCH ) );
    next = regnode( NOTHING );
    regtail( ret, next );
    regoptail( ret, next );
  }
  regparse++;
  if( ISMULT( *regparse ) ) {
    FAIL( "nested *?+" );
  }
  return( ret );
}

static char * regatom( int *flagp ) {
  register char *ret;
  int flags;
  *flagp = WORST;
  switch( *regparse++ ) {
    case '^':
      ret = regnode( BOL );
      break;
    case '$':
      ret = regnode( EOL );
      break;
    case '.':
      ret = regnode( ANY );
      *flagp |= HASWIDTH | SIMPLE;
      break;
    case '[': {
      register int classr;
      register int classend;
      if( *regparse == '^' ) {
        ret = regnode( ANYBUT );
        regparse++;
      } else
      { ret = regnode( ANYOF ); }
      if( *regparse == ']' || *regparse == '-' ) {
        regc( *regparse++ );
      }
      while( *regparse != '\0' && *regparse != ']' ) {
        if( *regparse == '-' ) {
          regparse++;
          if( *regparse == ']' || *regparse == '\0' ) {
            regc( '-' );
          } else {
            classr = UCHARAT( regparse - 2 ) + 1;
            classend = UCHARAT( regparse );
            if( classr > classend + 1 )
            { FAIL( "invalid [] range" ); }
            for( ; classr <= classend; classr++ )
            { regc( classr ); }
            regparse++;
          }
        } else
        { regc( *regparse++ ); }
      }
      regc( '\0' );
      if( *regparse != ']' ) {
        FAIL( "unmatched []" );
      }
      regparse++;
      *flagp |= HASWIDTH | SIMPLE;
    }
    break;
    case '(':
      ret = reg( 1, &flags );
      if( ret == NULL ) {
        return( NULL );
      }
      *flagp |= flags & ( HASWIDTH | SPSTART );
      break;
    case '\0':
    case '|':
    case '\n':
    case ')':
      FAIL( "internal urp" );
      break;
    case '?':
    case '+':
    case '*':
      FAIL( "?+* follows nothing" );
      break;
    case '\\':
      switch( *regparse++ ) {
        case '\0':
          FAIL( "trailing \\" );
          break;
        case '<':
          ret = regnode( WORDA );
          break;
        case '>':
          ret = regnode( WORDZ );
          break;
        default:
          goto de_fault;
      }
      break;
    de_fault:
    default: {
      char *regprev;
      register char ch;
      regparse--;
      ret = regnode( EXACTLY );
      for( regprev = 0 ; ; ) {
        ch = *regparse++;
        switch( *regparse ) {
          default:
            regc( ch );
            break;
          case '.':
          case '[':
          case '(':
          case ')':
          case '|':
          case '\n':
          case '$':
          case '^':
          case '\0':
          magic:
            regc( ch );
            goto done;
          case '?':
          case '+':
          case '*':
            if( !regprev )
            { goto magic; }
            regparse = regprev;
            goto done;
          case '\\':
            regc( ch );
            switch( regparse[1] ) {
              case '\0':
              case '<':
              case '>':
                goto done;
              default:
                regprev = regparse;
                regparse++;
                continue;
            }
        }
        regprev = regparse;
      }
    done:
      regc( '\0' );
      *flagp |= HASWIDTH;
      if( !regprev ) {
        *flagp |= SIMPLE;
      }
    }
    break;
  }
  return( ret );
}

static char * regnode( int op ) {
  register char *ret;
  register char *ptr;
  ret = regcode;
  if( ret == &regdummy ) {
    regsize += 3;
    return( ret );
  }
  ptr = ret;
  *ptr++ = op;
  *ptr++ = '\0';
  *ptr++ = '\0';
  regcode = ptr;
  return( ret );
}

static void regc( int b ) {
  if( regcode != &regdummy ) {
    *regcode++ = b;
  } else {
    regsize++;
  }
}

static void reginsert( char op, char *opnd ) {
  register char *src;
  register char *dst;
  register char *place;
  if( regcode == &regdummy ) {
    regsize += 3;
    return;
  }
  src = regcode;
  regcode += 3;
  dst = regcode;
  while( src > opnd ) {
    *--dst = *--src;
  }
  place = opnd;
  *place++ = op;
  *place++ = '\0';
  *place++ = '\0';
}

static void regtail( char *p, char *val ) {
  register char *scan;
  register char *temp;
  register int offset;
  if( p == &regdummy ) {
    return;
  }
  scan = p;
  for( ;; ) {
    temp = regnext( scan );
    if( temp == NULL ) {
      break;
    }
    scan = temp;
  }
  if( OP( scan ) == BACK ) {
    offset = scan - val;
  } else {
    offset = val - scan;
  }
  *( scan + 1 ) = ( offset >> 8 ) & 0377;
  *( scan + 2 ) = offset & 0377;
}

static void regoptail( char *p, char *val ) {
  if( p == NULL || p == &regdummy || OP( p ) != BRANCH ) {
    return;
  }
  regtail( OPERAND( p ), val );
}

static const char *reginput;
static char *regbol;
static const char **regstartp;
static const char **regendp;

STATIC int regtry( regexp *prog, const char *string );
STATIC int regmatch( char *prog );
STATIC int regrepeat( char *p );

int my_regexec( register regexp *prog, register const char *string ) {
  register char *s;
  if( prog == NULL || string == NULL ) {
    my_regerror( "NULL parameter" );
    return( 0 );
  }
  if( UCHARAT( prog->program ) != MAGIC ) {
    my_regerror( "corrupted program" );
    return( 0 );
  }
  if( prog->regmust != NULL ) {
    s = ( char * )string;
    while( ( s = strchr( s, prog->regmust[0] ) ) != NULL ) {
      if( strncmp( s, prog->regmust, prog->regmlen ) == 0 ) {
        break;
      }
      s++;
    }
    if( s == NULL ) {
      return( 0 );
    }
  }
  regbol = ( char * )string;
  if( prog->reganch ) {
    return( regtry( prog, string ) );
  }
  s = ( char * )string;
  if( prog->regstart != '\0' )
    while( ( s = strchr( s, prog->regstart ) ) != NULL ) {
      if( regtry( prog, s ) ) {
        return( 1 );
      }
      s++;
    } else
    do {
      if( regtry( prog, s ) ) {
        return( 1 );
      }
    } while( *s++ != '\0' );
  return( 0 );
}

static int regtry( regexp *prog, const char *string ) {
  register int i;
  register const char **sp;
  register const char **ep;
  reginput = string;
  regstartp = prog->startp;
  regendp = prog->endp;
  sp = prog->startp;
  ep = prog->endp;
  for( i = NSUBEXP; i > 0; i-- ) {
    *sp++ = NULL;
    *ep++ = NULL;
  }
  if( regmatch( prog->program + 1 ) ) {
    prog->startp[0] = string;
    prog->endp[0] = reginput;
    return( 1 );
  } else {
    return( 0 );
  }
}

static int regmatch( char *prog ) {
  register char *scan;
  char *next;
  scan = prog;
  while( scan != NULL ) {
    next = regnext( scan );
    switch( OP( scan ) ) {
      case BOL:
        if( reginput != regbol ) {
          return( 0 );
        }
        break;
      case EOL:
        if( *reginput != '\0' ) {
          return( 0 );
        }
        break;
      case WORDA:
        if( ( !isalnum( *reginput ) ) && *reginput != '_' ) {
          return( 0 );
        }
        if( reginput > regbol &&
            ( isalnum( reginput[-1] ) || reginput[-1] == '_' ) ) {
          return( 0 );
        }
        break;
      case WORDZ:
        if( isalnum( *reginput ) || *reginput == '_' ) {
          return( 0 );
        }
        break;
      case ANY:
        if( *reginput == '\0' ) {
          return( 0 );
        }
        reginput++;
        break;
      case EXACTLY: {
        register int len;
        register char *opnd;
        opnd = OPERAND( scan );
        if( *opnd != *reginput ) {
          return( 0 );
        }
        len = strlen( opnd );
        if( len > 1 && strncmp( opnd, reginput, len ) != 0 ) {
          return( 0 );
        }
        reginput += len;
      }
      break;
      case ANYOF:
        if( *reginput == '\0' || strchr( OPERAND( scan ), *reginput ) == NULL ) {
          return( 0 );
        }
        reginput++;
        break;
      case ANYBUT:
        if( *reginput == '\0' || strchr( OPERAND( scan ), *reginput ) != NULL ) {
          return( 0 );
        }
        reginput++;
        break;
      case NOTHING:
        break;
      case BACK:
        break;
      case OPEN+1:
      case OPEN+2:
      case OPEN+3:
      case OPEN+4:
      case OPEN+5:
      case OPEN+6:
      case OPEN+7:
      case OPEN+8:
      case OPEN+9: {
        register int no;
        register const char *save;
        no = OP( scan ) - OPEN;
        save = reginput;
        if( regmatch( next ) ) {
          if( regstartp[no] == NULL ) {
            regstartp[no] = save;
          }
          return( 1 );
        } else
        { return( 0 ); }
      }
      break;
      case CLOSE+1:
      case CLOSE+2:
      case CLOSE+3:
      case CLOSE+4:
      case CLOSE+5:
      case CLOSE+6:
      case CLOSE+7:
      case CLOSE+8:
      case CLOSE+9: {
        register int no;
        register const char *save;
        no = OP( scan ) - CLOSE;
        save = reginput;
        if( regmatch( next ) ) {
          if( regendp[no] == NULL ) {
            regendp[no] = save;
          }
          return( 1 );
        } else
        { return( 0 ); }
      }
      break;
      case BRANCH: {
        register const char *save;
        if( OP( next ) != BRANCH ) {
          next = OPERAND( scan );
        } else {
          do {
            save = reginput;
            if( regmatch( OPERAND( scan ) ) )
            { return( 1 ); }
            reginput = save;
            scan = regnext( scan );
          } while( scan != NULL && OP( scan ) == BRANCH );
          return( 0 );
        }
      }
      break;
      case STAR:
      case PLUS: {
        register char nextch;
        register int no;
        register const char *save;
        register int min;
        nextch = '\0';
        if( OP( next ) == EXACTLY ) {
          nextch = *OPERAND( next );
        }
        min = ( OP( scan ) == STAR ) ? 0 : 1;
        save = reginput;
        no = regrepeat( OPERAND( scan ) );
        while( no >= min ) {
          if( nextch == '\0' || *reginput == nextch )
            if( regmatch( next ) )
            { return( 1 ); }
          no--;
          reginput = save + no;
        }
        return( 0 );
      }
      break;
      case END:
        return( 1 );
        break;
      default:
        my_regerror( "内存损坏" );
        return( 0 );
        break;
    }
    scan = next;
  }
  my_regerror( "损坏的指针" );
  return( 0 );
}

static int regrepeat( char *p ) {
  register int count = 0;
  register const char *scan;
  register char *opnd;
  scan = reginput;
  opnd = OPERAND( p );
  switch( OP( p ) ) {
    case ANY:
      count = strlen( scan );
      scan += count;
      break;
    case EXACTLY:
      while( *opnd == *scan ) {
        count++;
        scan++;
      }
      break;
    case ANYOF:
      while( *scan != '\0' && strchr( opnd, *scan ) != NULL ) {
        count++;
        scan++;
      }
      break;
    case ANYBUT:
      while( *scan != '\0' && strchr( opnd, *scan ) == NULL ) {
        count++;
        scan++;
      }
      break;
    default:
      my_regerror( "内部故障" );
      count = 0;
      break;
  }
  reginput = scan;
  return( count );
}

static char * regnext( register char *p ) {
  register int offset;
  if( p == &regdummy ) {
    return( NULL );
  }
  offset = NEXT( p );
  if( offset == 0 ) {
    return( NULL );
  }
  if( OP( p ) == BACK ) {
    return( p - offset );
  } else {
    return( p + offset );
  }
}

void my_regerror( const char *s ) {
  printf( "re error %s\n", s );
}

void my_redone( regexp *re ) {
  if( re ) {
    free( ( char * ) re );
  }
}
